import java.io.IOException;
import java.util.*;

/*
 * AVL дерево. Дерево строится по ключу (key). Данные хранятся в типе T (value)
 */
abstract public class AVLTree<T> {

    Node<T> root;

    // Rotate subtree rooted with y
    private Node<T> rightRotate(final Node<T> y) {
        final Node<T> x = y.left();
        final Node<T> T3 = x.right();
        x.right = y;
        y.left = T3;
        y.height();
        x.height();
        return x;
    }

    // Rotate subtree rooted with x
    private Node<T> leftRotate(final Node<T> x) {
        final Node<T> y = x.right();
        final Node<T> T2 = y.left();
        y.left = x;
        x.right = T2;
        x.height();
        y.height();
        return y;
    }

    private Node<T> insert(final Node<T> node, final Word key, final T value) {
        if (node == null) {
            return newNode(key, value);
        }

        final int cmp = key.compareTo(node.key);
        if (cmp < 0) { // data < node.data
            node.left = insert(node.left(), key, value);
        } else if (cmp > 0) {
            node.right = insert(node.right(), key, value);
        } else {
            throw new UnsupportedOperationException("Dulicate key - '" + key + "'"); // дублирующиеся значения ключа
                                                                                     // вставлять нельзя
        }
        node.height();
        int balance = node.balance();

        // Left Left Case
        if (balance > 1 && key.compareTo(node.left().key) < 0) { // data < node.left.data
            return rightRotate(node);
        }

        // Right Right Case
        if (balance < -1 && key.compareTo(node.right().key) > 0) { // data > node.right.data
            return leftRotate(node);
        }

        // Left Right Case
        if (balance > 1 && key.compareTo(node.left().key) > 0) { // data > node.left.data
            node.left = leftRotate(node.left());
            return rightRotate(node);
        }

        // Right Left Case
        if (balance < -1 && key.compareTo(node.right().key) < 0) {
            node.right = rightRotate(node.right());
            return leftRotate(node);
        }
        return node;
    }

    final public void put(final Word key, final T v) {
        root = insert(root, key, v);
    }

    final public Node<T> get(final String key) {
        return get(new Word(key));
    }

    final public Node<T> get(final Word key) {
        Node<T> trav = root;
        while (trav != null) {
            int cmp = key.compareTo(trav.key);
            if (cmp < 0) {
                trav = trav.left();
            } else if (cmp > 0) {
                trav = trav.right();
            } else {
                return trav;
            }
        }
        return null;
    }

    /**
     * Поиск в дереве индекса поддерева, соответствующего шаблону
     * 
     * @param pattern - шаблон, по которому выполняем поиск
     * @return - корень поддерева
     */
    final public Node<T> getSubtreeByPattern(final WordIndex pattern) {
        Node<T> trav = root;
        while (trav != null) {
            int cmp = pattern.compareToPrefix(trav.key);
            if (cmp < 0) {
                trav = trav.left();
            } else if (cmp > 0) {
                trav = trav.right();
            } else {
                return trav;
            }
        }
        return null;
    }

    /**
     * Дополнение к getSubtreeByPattern. Выполняет тоже самое, но возвращает высоту
     * узла, а не узел. Если в Node переменную height не использовать как id, то
     * тогда можно было бы использовать переменную height у возвращаемого значения
     * метода getSubtreeByPattern.
     * 
     * @param pattern - шаблон, по которому выполняем поиск
     * @return - высота поддерева, соотвествующему pattern, относительно вершины
     */
    final public int getSubtreeHeight(final WordIndex pattern) {
        Node<T> trav = root;
        int c = 0;
        while (trav != null) {
            int cmp = pattern.compareToPrefix(trav.key);
            if (cmp < 0) {
                trav = trav.left();
                c++;
            } else if (cmp > 0) {
                trav = trav.right();
                c++;
            } else {
                return c;
            }
        }
        return -1;
    }

    /**
     * Поиск в дереве, в котором элементы пронумерованы в порядке обхода дерева.
     * Обход начинается с корня и выполняется слева направо.
     * 
     * @param id - id, который надо найти
     * @return - узел с требуемым id
     */
    final public Node<T> getNodeById(final int id) {
        Node<T> trav = root;
        while (trav != null) {
            if (trav.getId() == id)
                return trav;

            if (trav.right != null) {
                if (trav.right instanceof Integer) {
                    if ((Integer) trav.right <= id) {
                        throw new UnsupportedOperationException("Something wrong");
                    } else {
                        trav = trav.left();
                    }
                } else {
                    if (trav.right().getId() <= id) {
                        trav = trav.right();
                    } else {
                        trav = trav.left();
                    }
                }
            } else {
                trav = trav.left();
            }
        }
        return null;
    }

    final public boolean isEmpty() {
        return (root == null);
    }

    /*
     * Загрузка данных в value. Реализация меняется в зависимости от типа
     * данных, хранящихся в дереве.
     */
    abstract T loadValue(TreeReader<T> jo);

    /**
     * Вызов конструктора узла. Вызывается при построении дерева
     */
    abstract Node<T> newNode(Word key, T value);

    /**
     * Вызов конструктора узла. Вызывается при загрузке дерева из файла
     */
    abstract Node<T> newNode(Word key, T value, TreeReader<T> reader);

    /*
     * Универсальная функция загрузки данных в дерево.
     * Узлы дерева должны располагаться в порядке следования в дереве, то есть
     * запись файла должна быть выполнена с помощью итератора StoreIteratorAbstract.
     */
    final public void load(TreeReader<T> parser) throws IOException {
        /*
         * предыдущий узел, т.е. тот который обрабатывался на предыдущей итерации цикла.
         * С высокой долей вероятности он и будет родительским для текущего.
         * Это оптимизация, чтобы по Id не находить родителя в дереве.
         */
        Node<T> prevnode = null;
        while (parser.next()) {
            if (parser.isDelimiter()) // разделитель
                return;

            ArrayList<Object> parserData = parser.parse1();
            final Integer id = (Integer) parserData.get(0);
            final Integer left = (Integer) parserData.get(1);
            final Integer right = (Integer) parserData.get(2);
            final Integer parent = (Integer) parserData.get(3);
            final Word key = (Word) parserData.get(4);
            final T value = loadValue(parser);

            Node<T> node;
            Node<T> parentNode;
            if (left == null && right == null) { // это лист, создаем его сразу Node
                node = newNode(key, value, parser);
                node.setId(id);
                if (parent == null) { // справочник из одного элемента
                    root = node;
                    continue;
                }
                if (prevnode != null && prevnode.getId() == parent)
                    parentNode = prevnode; // оптимизация. См описание prevnode
                else
                    parentNode = getNodeById(parent);
            } else { // Это не лист, создаем его Node, в котором хранятся ID узлов.
                node = newNode(key, value, parser);
                node.setId(id);
                node.left = left;
                node.right = right;
                if (parent == null) {
                    root = node;
                    prevnode = node;
                    continue;
                }
                if (prevnode != null && prevnode.getId() == parent)
                    parentNode = prevnode; // оптимизация. См описание prevnode
                else
                    parentNode = getNodeById(parent);
                prevnode = node;
            }

            // заменяет у родителя id узла на реального потомка
            if (parentNode.left instanceof Integer && (Integer) parentNode.left == (int) id) {
                parentNode.left = node;
            } else if (parentNode.right instanceof Integer && (Integer) parentNode.right == (int) id) {
                parentNode.right = node;
            }
        }
    }

    /*
     * Обход дерева слева направо.
     * Элементы выдаются в порядке возрастания значения ключа.
     * Используется в запросе filterKey
     */
    final class RefIterator implements Iterator<Node<T>> {
        final Stack<Node<T>> stack = new Stack<Node<T>>();
        int count = 0;
        Node<T> trav;

        RefIterator() {
            trav = AVLTree.this.root;
            if (trav == null) {
                throw new UnsupportedOperationException();
            }
            stack.push(trav);
        }

        RefIterator(Node<T> subroot) {
            trav = subroot;
            if (trav == null) {
                throw new UnsupportedOperationException();
            }
            stack.push(trav);
        }

        @Override
        public boolean hasNext() {
            return !stack.isEmpty();
        }

        @Override
        public Node<T> next() {
            while (trav.left != null) {
                trav = trav.left();
                stack.push(trav);
            }

            Node<T> node = stack.pop();

            if (node.right != null) {
                trav = node.right();
                stack.push(trav);
            }

            count++;
            return node;
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }

    /*
     * Обход дерева слева направо.
     * Элементы выдаются в порядке возрастания значения ключа.
     * 
     * Отличие от Iterator - итерация иден не только по дереву, но и по
     * содержимому value в дереве index.
     * 
     * Итератор для выполнения поиска по дереву index слов (ключей), соответствующих
     * шаблону. Ключа - всегда Word (в win1251).
     *
     */
    final class LikeIterator implements Iterator<T> {
        private Node<T> trav;
        private final Stack<Node<T>> stack = new Stack<Node<T>>();

        PatternSearch patsearch;
        Iterable<Node<RefData>> portion = null;
        Iterator<Node<RefData>> portionIter;

        public LikeIterator(Node<T> subroot) {
            trav = (subroot != null) ? subroot : root;
            if (trav == null) {
                throw new UnsupportedOperationException();
            }
            stack.push(trav);
        }

        /*
         * Получить следующую запись в индексе.
         */
        @SuppressWarnings("unchecked")
        public final Node<RefData> nextDataNode() {
            if (portion != null && portionIter.hasNext()) {
                return portionIter.next();
            }
            // дошли до конца порции или это самая первая порция
            portion = (Iterable<Node<RefData>>) next();
            if (portion == null)
                return null;
            portionIter = portion.iterator();

            return portionIter.next();
        }

        @SuppressWarnings("unchecked")
        public final void nextIndexNode() {
            portion = (Iterable<Node<RefData>>) next();
            if (portion != null)
                portionIter = portion.iterator();
        }

        @Override
        public final boolean hasNext() {
            return !stack.isEmpty() || (portion != null && portionIter.hasNext());
        }

        @Override
        /*
         * поиск по дереву происходится только по одному слову, т.к. в ключах дерева
         * index лежат только слова
         * 
         * Для дерева индекса в нодах хранятся массивы, метод вернет массив,
         * для итерирования массивов надо вызывать nextNode, которая будет вызывать
         * next()
         */
        public final T next() {
            while (trav.left != null) {
                trav = trav.left();
                stack.push(trav);
            }

            Node<T> node = stack.pop();
            T res = node.value;

            if (node.right != null) {
                trav = node.right();
                stack.push(trav);
            }

            return (patsearch.index(node.key.value) >= 0) ? res : null;
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }

    /*
     * Обход дерева слева направо в порядке расположения узлов в дереве.
     * Используется в сериализации дерева
     */
    abstract class StoreIteratorAbstract implements Iterator<Node<T>> {
        final Stack<Node<T>> stack = new Stack<Node<T>>();
        final Stack<Integer> dir = new Stack<Integer>();
        final Stack<Object[]> listStack = new Stack<Object[]>();
        Node<T> trav = null;
        Object[] rec;
        int trav_dir = 0; // 0 - left, 1 - right, 2 - up direction
        int count = 0;

        StoreIteratorAbstract() {
            if (AVLTree.this.root == null) {
                throw new UnsupportedOperationException();
            }
        }

        @Override
        public final boolean hasNext() {
            return !stack.empty() || trav_dir <= 1;
        }

        abstract Object[] storeNode(final Node<T> node);

        @Override
        public final Node<T> next() {
            if (trav == null) {
                trav = root;

                count++;
                rec = storeNode(trav);

                if (trav.left == null && trav.right == null) { // дерево из одного элемента. Обход окончен.
                    trav_dir = 2;
                }
                return trav;
            }
            while (!stack.empty() || trav_dir <= 1) { // завершение, если находимся в корне и обошли left + right
                if (trav_dir == 0) {
                    if (trav.left != null) {
                        stack.push(trav);
                        dir.push(trav_dir);
                        trav = trav.left();
                        trav_dir = 0;

                        count++;
                        rec[1] = count; // заполняем левого потомка
                        listStack.push(rec);
                        rec = storeNode(trav);
                        return trav;
                    } else {
                        trav_dir++; // меняем направление движения слева (0) направо (1)
                    }
                } else if (trav_dir == 1) {
                    if (trav.right != null) {
                        stack.push(trav);
                        dir.push(trav_dir);
                        trav = trav.right();
                        trav_dir = 0;

                        count++;
                        rec[2] = count; // заполняем правого потомка
                        listStack.push(rec);
                        rec = storeNode(trav);
                        return trav;
                    } else {
                        if (!stack.isEmpty()) { // Условие срабатывает в единственном случае - дерево из 2-х элементов и
                                                // у корня right==null
                            trav = stack.pop();
                            trav_dir = dir.pop();
                            rec = listStack.pop();
                        }
                        trav_dir++;
                    }
                } else {
                    trav = stack.pop();
                    trav_dir = dir.pop();
                    rec = listStack.pop();
                    trav_dir++;
                }
            }
            return null;
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }
}